package leetcode.leetcode_hot100;

import java.util.*;

public class T0301 {
    private int len;
    private char[] charArray;
    private Set<String> validExpressions = new HashSet<>();

    public List<String> removeInvalidParentheses(String s) {
        this.len = s.length();
        this.charArray = s.toCharArray();

        // 第 1 步：遍历一次，计算多余的左右括号
        int leftRemove = 0;
        int rightRemove = 0;
        for (int i = 0; i < len; i++) {
            if (charArray[i] == '(') {
                leftRemove++;
            } else if (charArray[i] == ')') {
                // 遇到右括号的时候，须要根据已经存在的左括号数量决定
                if (leftRemove == 0) {
                    rightRemove++;
                }
                if (leftRemove > 0) {
                    // 关键：一个右括号出现可以抵销之前遇到的左括号
                    leftRemove--;
                }
            }
        }

        // 第 2 步：回溯算法，尝试每一种可能的删除操作
        StringBuilder path = new StringBuilder();
        dfs(0, 0, 0, leftRemove, rightRemove, path);
        return new ArrayList<>(this.validExpressions);
    }

    /**
     * @param index       当前遍历到的下标
     * @param leftCount   已经遍历到的左括号的个数
     * @param rightCount  已经遍历到的右括号的个数
     * @param leftRemove  最少应该删除的左括号的个数
     * @param rightRemove 最少应该删除的右括号的个数
     * @param path        一个可能的结果
     */
    private void dfs(int index, int leftCount, int rightCount, int leftRemove, int rightRemove, StringBuilder path) {
        if (index == len) {
            if (leftRemove == 0 && rightRemove == 0) {
                validExpressions.add(path.toString());
            }
            return;
        }

        char character = charArray[index];
        // 可能的操作 1：删除当前遍历到的字符
        if (character == '(' && leftRemove > 0) {
            // 由于 leftRemove > 0，并且当前遇到的是左括号，因此可以尝试删除当前遇到的左括号
            dfs(index + 1, leftCount, rightCount, leftRemove - 1, rightRemove, path);
        }
        if (character == ')' && rightRemove > 0) {
            // 由于 rightRemove > 0，并且当前遇到的是右括号，因此可以尝试删除当前遇到的右括号
            dfs(index + 1, leftCount, rightCount, leftRemove, rightRemove - 1, path);
        }

        // 可能的操作 2：保留当前遍历到的字符
        path.append(character);
        if (character != '(' && character != ')') {
            // 如果不是括号，继续深度优先遍历
            dfs(index + 1, leftCount, rightCount, leftRemove, rightRemove, path);
        } else if (character == '(') {
            // 考虑左括号
            dfs(index + 1, leftCount + 1, rightCount, leftRemove, rightRemove, path);
        } else if (rightCount < leftCount) {
            // 考虑右括号
            dfs(index + 1, leftCount, rightCount + 1, leftRemove, rightRemove, path);
        }
        path.deleteCharAt(path.length() - 1);
    }
    class Solution2 {

        public List<String> removeInvalidParentheses(String s) {
            List<String> res = new ArrayList<>();
            if (s == null) {
                return res;
            }

            // 广度优先遍历须要的队列和防止重复遍历的哈希表 visited
            Set<String> visited = new HashSet<>();
            visited.add(s);
            Queue<String> queue = new LinkedList<>();
            queue.add(s);

            // 找到目标值以后推出循环
            boolean found = false;
            while (!queue.isEmpty()) {
                // 最优解一定在同一层
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    String front = queue.poll();
                    if (isValid(front)) {
                        res.add(front);
                        found = true;
                    }

                    int currentWordLen = front.length();
                    char[] charArray = front.toCharArray();
                    for (int j = 0; j < currentWordLen; j++) {
                        if (front.charAt(j) != '(' && front.charAt(j) != ')') {
                            continue;
                        }

                        // 注意 new String() 方法的 API，第 1 个参数是字符数组，第 2 个参数是字符数组的起始下标，第 3 个参数是截取的字符的长度
                        String next = new String(charArray, 0, j) + new String(charArray, j + 1, currentWordLen - j - 1);
                        if (!visited.contains(next)) {
                            queue.offer(next);
                            visited.add(next);
                        }
                    }
                }

                // 这一层找到以后，退出外层循环，返回结果
                if (found) {
                    break;
                }
            }
            return res;
        }

        public boolean isValid(String s) {
            char[] charArray = s.toCharArray();
            int count = 0;
            for (char c : charArray) {
                if (c == '(') {
                    count++;
                } else if (c == ')') {
                    count--;
                }
                if (count < 0) {
                    return false;
                }
            }
            return count == 0;
        }
    }
    class Solution3 {
        public List<String> removeInvalidParentheses(String s) {
            Set<String> set = new HashSet<>();
            List<String> ans = new ArrayList<>();
            set.add(s);
            while (true) {
                for (String str : set) {
                    if (isRegular(str))
                        ans.add(str);
                }
                if (ans.size() > 0) return ans;
                Set<String> nextSet = new HashSet<>();
                for (String str : set) {
                    for (int i = 0; i < str.length(); i ++) {
                        if (str.charAt(i) == '(' || str.charAt(i) == ')')
                            nextSet.add(str.substring(0, i) + str.substring(i + 1, str.length()));
                    }
                }
                set = nextSet;
            }
        }

        public boolean isRegular(String s) {
            char[] ss = s.toCharArray();
            int count = 0;
            for (char c : ss) {
                if (c == '(') count ++;
                else if (c == ')') count --;
                if (count < 0) return false;
            }
            return count == 0;
        }
    }
    class Solution4 {
        int len;
        public List<String> removeInvalidParentheses(String s) {
            char[] cs = s.toCharArray();
            int l = 0, r = 0;
            for (char c : cs) {
                if (c == '(') {
                    l++;
                } else if (c == ')') {
                    r++;
                }
            }
            int max = Math.min(l, r);
            Set<String> all = new HashSet<>();
            dfs(cs, 0, 0, max, "", all);
            List<String> ans = new ArrayList<>();
            for (String str : all) {
                if (str.length() == len) ans.add(str);
            }
            return ans;
        }
        /**
         * cs: 字符串 s 对应的字符数组
         * u: 当前决策到 cs 的哪一位
         * score: 当前决策方案的得分值（每往 cur 追加一个左括号进行 +1；每往 cur 追加一个右括号进行 -1）
         * max: 整个 dfs 过程的最大得分
         * cur: 当前决策方案
         * ans: 合法方案结果集
         */
        void dfs(char[] cs, int u, int score, int max, String cur, Set<String> ans) {
            if (u == cs.length) {
                if (score == 0 && cur.length() >= len) {
                    len = Math.max(len, cur.length());
                    ans.add(cur);
                }
                return;
            }
            if (cs[u] == '(') {
                if (score + 1 <= max) dfs(cs, u + 1, score + 1, max, cur + "(", ans);
                dfs(cs, u + 1, score, max, cur, ans);
            } else if (cs[u] == ')') {
                if (score > 0) dfs(cs, u + 1, score - 1, max, cur + ")", ans);
                dfs(cs, u + 1, score, max, cur, ans);
            } else {
                dfs(cs, u + 1, score, max, cur + String.valueOf(cs[u]), ans);
            }
        }
    }
}
